package linkedlist;

public class MyLinkedList {
    static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    '}';
        }
    }
    public ListNode head; //代表当前链表的头结点

    public void createNode(){
        ListNode listNode1 = new ListNode(13);
        ListNode listNode2 = new ListNode(35);
        ListNode listNode3 = new ListNode(19);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        head = listNode1;
    }
    public void print(){ // 打印链表的每个值
        ListNode cur = head;
        while (cur!=null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void print(ListNode head){ // 从指定位置打印链表的每个值
        ListNode cur = head;
        while (cur!=null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public int size(){  // 获取链表长度
        int count = 0;
        ListNode cur = head;
        while (cur!=null) {
            cur = cur.next;
            count++;
        }
        return count;
    }
    public boolean contains(int key){ //查找链表中是否有某个值
        ListNode cur = head;
        while (cur!=null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    public void addFirst(int data){ // 头插法
        ListNode listNode = new ListNode(data);
        listNode.next = head;
        head = listNode;
    }
    public void addLast(int data){ // 尾插法
        ListNode listNode = new ListNode(data);
        ListNode cur = head;
        while (cur != null){
            if(cur.next == null){
                cur.next = listNode;
                break;
            }
            cur = cur.next;
        }
        if(head == null){
            head = listNode;
        }
    }
    private void checkIndex(int index){  // 检查index位置是否合法
        if(index < 0 || index > size()){
            throw new LinkedListIndexOutOfException("index位置不合法");
        }
    }
    public void addIndex(int index, int data){  //指定位置插入
        ListNode cur = head;
        ListNode listNode = new ListNode(data);
        checkIndex(index);
        if(index == 0){
            addFirst(data);
        } else if(index == size()){
            addLast(data);
        } else {
            for (int i = 0; i < index; i++) {
                if(i == index - 1){
                    listNode.next = cur.next;
                    cur.next = listNode;
                    break;
                }
                cur = cur.next;
            }
        }
    }
    public void removeData (int data){ // 删除第一个值为data的节点
        if(head == null){
            System.out.println("链表为空，不可删除");
            return;
        }
        ListNode cur = head;
        if(head.val == data){  //  如果头节点值为data
            head = head.next;  //直接删除 返回
            return;
        }
        while (cur.next != null) {
            if(cur.next.val == data){
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }
        System.out.println("删除失败");
    }
    public void removeAll(int data){ // 删除所有值为data的节点
        if(head == null){
            return;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        while (cur != null){  // 先从第二个节点开始删除
            if(cur.val == data){  // 如果cur值是data
                pre.next = cur.next;
            } else {  // 如果cur值不是data
                pre = cur;
            }
            cur = cur.next;
        }
        if(head.val == data){  //然后判断第一个节点值是否为data
            head = head.next;
        }
    }
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) { //合并两个有序链表
        ListNode head = new ListNode(0);
        ListNode temp = head;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                temp.next = list2;
                list2 = list2.next;
            } else {
                temp.next = list1;
                list1 = list1.next;
            }
            temp = temp.next;
        }
        if (list1 != null) {
            temp.next = list1;
        }
        if (list2 != null) {
            temp.next = list2;
        }
        return head.next;
    }
    public void clear(){ // 清空链表
        head = null;
    }
}
